2-4. Exercise

https://introtcs.org/public/lec_02_representation.html#exercises

이 모든 문제들에 대해 진지하게 다 증명하지는 않을거고 그냥 이해만 하고 넘어가야겠다.

Binary representation

a. 함수 NtS, 자연수를 이진수열로 만드는 함수가 다음 조건을 만족하는지 증명하시오. NtS(n)의 결과를 x라고 했을때,

• x의 길이가 1 + max(0,[log2n]) 라는것.
• x의 i 번째 숫자가 ⌊x/2⌊log2​n⌋−i⌋ mod 2 와 같다는 것. (log2n에서 i를 뺀 정수를 a 라고 하면. 2^a 제곱으로 x를 나눈 정수값을 2로 나눈 나머지와 같은가?)

b. StN(역으로 이진수열을 자연수로 만드는 함수)을 가지고 NtS가 1-1 함수임을 증명하시오.

More Compact than ASCII representation

1. 알파벳 {a,b,c, ...., z}에 속하는 문자들 n개로 이루어진 문자열 x가 있으면, $E(x)$의 길이가 최대 $4.8n + 1000$가 되는 1-1 인코딩 함수 E가 있음을 증명하시오.
2. $E(x)$의 길이가 $4.6n+1000$이 되는 1-1 함수가 없음을 증명하시오. (1-1 함수가 아니다 = 어떤 n에서는 인코딩 결과가 겹친다?) (그러니까
3. 파이썬의 bz2.compress 함수는 loseless(그러므로 1-1,단사 함수) 압축 방법이다. 톨스토이의 "전쟁과 평화를" 위의 규칙에 맞게끔 전부 알파벳 소문자로만 만들고 bz2.compress를 실행하면 $k = 6,274,768$이 나온다고. 압축하기 전의 전쟁과 평화의 글자수는 $n = 2,517,262$ 글자로 이루어져있다. 위에서는 최대 $4.8n+1000$ 길이로 된 이진수열로는 중복 없이 변환하는게 가능하지만 $4.6n+1000$ 밑으로는 중복이 있을 수 밖에 없다고 했는데. $k = 2.49n$에 불과하다. 이게 앞에 증명들과 모순되지 않는다는걸 증명하시오.
4. 흥미롭게도, 무작위random한 문자열을 가지고 bz2.compress를 실행하면 효율이 좋지 않다 (교재 예시는 4.78까지 나왔다고 한다). 누군가가 새로운 방법을 도입해서 완전히 무작위한 문자열을 4.6n길이 밑으로 성공적으로(1-1로) 변환하는데 성공했다고 한다. 이게 모든 n > 100에 대해서 적용되지는 않는다는 것을 증명하시오.(Z 가 100글자 이상으로 이루어진 문자열 x를 E(x) 했을때 나올 이진수열의 길이라고 하면 Z의 기대값이 최소 4.6n임을 증명)

Representing graphs: upper bound.

최대 10의 차수를 가지는 노드들 n개로 이루어진 방향 그래프([n]= [3]이면 {1,2,3}, [5]면 {1,2,3,4,5} 처럼 1부터 n까지라는 패턴을 가지는 정수들의 집합)가 있다. 이걸 이진수열로 최대 1000n logn 비트의 길이를 가지는 이진수열로 변환하는 함수 E가 있음을 증명하시오.

Representing graphs: lower bound.

1. Sn 함수가 있고 이 함수가 [n] -> [n] 대응시키는 1-1함수면서 전사함수라고 하고. 최대 10의 차수를 가진 2n개의 노드로 이루어진 그래프에 대해서도 Sn 함수가 1-1 함수라는것을 증명하라.
   Sn이 [n]->[n] 대응시키는 1-1함수이면서, 전사함수인 함수들의 집합이다? 이건 순열을 의미한다.
   즉 {1,2,3, ..., n} 까지의 순열의 개수가 10개의 차수를 가지는 2n개의 노드로 이루어진 그래프의 개수보다 작다(이하)는걸 증명하라.
2. 위의 문제 upper bound에서 최대 1000n logn 비트 길이로 '최대 10의 차수를 가진 n개의 노드를 가진 그래프 G'를 인코딩할 수 있다고 했는데, $0.001n logn + 1000$ 비트 길이의 이진수열에는 1-1함수가 없다는 것을 증명하라.
   즉 최소 $0.0001n logn + 1000$개 비트가 필요하다는걸 증명하라.